package main

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	pathP := []*TreeNode{}
	pathQ := []*TreeNode{}
	temp := root
	for temp != nil {
		pathP = append(pathP, temp)
		if temp.Val == p.Val {
			break
		}
		if p.Val < temp.Val {
			temp = temp.Left
		} else {
			temp = temp.Right
		}
	}
	temp = root
	for temp != nil {
		pathQ = append(pathQ, temp)
		if temp.Val == q.Val {
			break
		}
		if q.Val > temp.Val {
			temp = temp.Right
		} else {
			temp = temp.Left
		}
	}
	for i := 0; i < len(pathQ) && i < len(pathP); i++ {
		if pathQ[i] != pathP[i] {
			return pathP[i-1]
		}
	}
	if len(pathP) > len(pathQ) {
		return pathQ[len(pathQ)-1]
	} else {
		return pathP[len(pathP)-1]
	}
}

func main() {

}
